<html lang="en">
<head>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">

<link type="text/css" rel="stylesheet" href="../source/css/bootstrap.css" />
<link type="text/css" rel="stylesheet" href="../source/css/bootstrap-responsive.css" />
<link type="text/css" rel="stylesheet" href="../source/css/docs.css" />
<link type="text/css" rel="stylesheet" href="../source/css/monokai.css" />
<link type="text/css" rel="stylesheet" href="../source/css/font-awesome.css">

<script type="text/javascript" src="../source/js/jquery-1.9.1.js"></script>
<script type="text/javascript" src="../source/js/bootstrap.js"></script>
<script type="text/javascript" src="../source/js/highlight.pack.js"></script>
<script type="text/x-mathjax-config"> 
    MathJax.Hub.Config({ 
        tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} 
    }); 
</script>
<script type="text/javascript"
    src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>20171026</title>

</head>
<body data-spy="scroll" data-target=".bs-docs-sidebar">
<div class="navbar navbar-fixed-top">
    <div class="navbar-inner">
        <div class="container">
            <!-- .btn-navbar is used as the toggle for collapsed navbar content -->
            <a class="btn btn-navbar" data-toggle="collapse" data-target=".nav-collapse">
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
            </a>

            <!-- Be sure to leave the brand out there if you want it shown -->
            <a class="brand" href="../index.html">Wahacer's blogs</a>

            <!-- Everything you want hidden at 940px or less, place within here -->
            <div class="nav-collapse collapse">
                <!-- .nav, .navbar-search, .navbar-form, etc -->
                <ul class="nav">
                    <li class="">
                        <a href="../index.html">Index</a>
                    </li>
                    
                    <li class="">
                        <a href="../Solution/index.html">Solution</a>
                    </li>
                    
                    <li class="">
                        <a href="../Algorithm/index.html">Algorithm</a>
                    </li>
                    

                </ul>
            </div>
        </div>
    </div>
</div>

<div class="container-fluid">
    <div class="row-fluid">
        <!--　侧边拦 -->
        <div class="span2 bs-docs-sidebar">
            <br><br><br>
            <div align="center"><img src="../source/picture/photo.jpg" alt="photo" width="250" height="250" /></div>
            <p align="center"><strong>Wahacer</strong></p>

        </div>

        <!-- 主内容　-->
        <div class="span8">
            <br>
            <!--Body content-->
            <h2 id="toc-0">Noip2013 Day1</h2>
<p>题面</p>
<p><img src="https://s1.ax1x.com/2017/10/26/UJAw4.png" alt=""></p>
<p>概括一下题面：编号0-n-1个孩子围一圈，顺时针走m个位置，进行10^k轮，问第x号孩子玩完以后 <del>会不会转死</del> 的位置.</p>
<p>看数据发现一脸不可做，30%就是手动模拟，最多10^7轮，一轮一轮模拟还是可以30分.</p>
<p>于是考试的时候拿数据暴力模拟，似乎推出了几个结论?<del>其实都是题目中给的</del></p>
<p>可以知道每n轮一循环。</p>
<p>每一轮：</p>
<blockquote><p>对于每个位置，编号为(x-m+n)%n，x是当前的编号.</p>
<p>对于每一个编号，编号为x的人，一轮过后会走到x+m这个号的位置上去.</p>
</blockquote>
<p>所以这道题就是要求</p>
<p>$$((10^k).Mod.N + ss*m)Mod.N $$</p>
<p>那么就可以发现对于100%的数据,k&lt;=10^7.</p>
<p>所以高精度模板题</p>
<div class="highlight"><pre><span></span><span class="cp">#include</span><span class="cpf">&lt;cstdio&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cstring&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cmath&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;iostream&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;algorithm&gt;</span><span class="cp"></span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span> <span class="p">;</span>
<span class="cp">#define ll long long</span>
<span class="k">template</span><span class="o">&lt;</span><span class="k">class</span> <span class="nc">T</span><span class="o">&gt;</span><span class="kt">void</span> <span class="n">read</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">){</span>
    <span class="n">x</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">int</span> <span class="n">f</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">char</span> <span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;</span><span class="sc">&#39;0&#39;</span><span class="o">||</span><span class="n">ch</span><span class="o">&gt;</span><span class="sc">&#39;9&#39;</span><span class="p">){</span><span class="n">f</span><span class="o">|=</span><span class="p">(</span><span class="n">ch</span><span class="o">==</span><span class="sc">&#39;-&#39;</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;=</span><span class="sc">&#39;9&#39;</span><span class="o">&amp;&amp;</span><span class="n">ch</span><span class="o">&gt;=</span><span class="sc">&#39;0&#39;</span><span class="p">){</span><span class="n">x</span><span class="o">=</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">3</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">ch</span><span class="o">^</span><span class="mi">48</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="n">x</span><span class="o">=</span><span class="n">f</span><span class="o">?-</span><span class="nl">x</span><span class="p">:</span><span class="n">x</span><span class="p">;</span>
    <span class="k">return</span> <span class="p">;</span>
<span class="p">}</span>

<span class="n">ll</span> <span class="n">pow</span><span class="p">(</span><span class="n">ll</span> <span class="n">a</span><span class="p">,</span><span class="n">ll</span> <span class="n">b</span><span class="p">,</span><span class="n">ll</span> <span class="n">mod</span><span class="p">)</span>
<span class="p">{</span>
    <span class="n">ll</span> <span class="n">ans</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span>
    <span class="k">while</span><span class="p">(</span><span class="n">b</span><span class="p">){</span>
        <span class="k">if</span><span class="p">(</span><span class="n">b</span><span class="o">&amp;</span><span class="mi">1</span><span class="p">)</span> <span class="p">(</span><span class="n">ans</span><span class="o">*=</span><span class="n">a</span><span class="p">)</span><span class="o">%=</span><span class="n">mod</span><span class="p">;</span>
        <span class="p">(</span><span class="n">a</span><span class="o">*=</span><span class="n">a</span><span class="p">)</span><span class="o">%=</span><span class="n">mod</span><span class="p">;</span> 
        <span class="n">b</span><span class="o">&gt;&gt;=</span><span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">ans</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="n">main</span><span class="p">()</span>
<span class="p">{</span>
    <span class="n">freopen</span><span class="p">(</span><span class="s">&quot;circle.in&quot;</span><span class="p">,</span><span class="s">&quot;r&quot;</span><span class="p">,</span><span class="n">stdin</span><span class="p">);</span>
    <span class="n">freopen</span><span class="p">(</span><span class="s">&quot;circle.out&quot;</span><span class="p">,</span><span class="s">&quot;w&quot;</span><span class="p">,</span><span class="n">stdout</span><span class="p">);</span>
    <span class="kt">long</span> <span class="kt">long</span> <span class="n">n</span><span class="p">,</span><span class="n">m</span><span class="p">,</span><span class="n">k</span><span class="p">,</span><span class="n">x</span><span class="p">;</span>
    <span class="n">read</span><span class="p">(</span><span class="n">n</span><span class="p">),</span><span class="n">read</span><span class="p">(</span><span class="n">m</span><span class="p">),</span><span class="n">read</span><span class="p">(</span><span class="n">k</span><span class="p">),</span><span class="n">read</span><span class="p">(</span><span class="n">x</span><span class="p">);</span>
    <span class="kt">long</span> <span class="kt">long</span> <span class="n">ss</span><span class="o">=</span><span class="n">pow</span><span class="p">(</span><span class="mi">10</span><span class="p">,</span><span class="n">k</span><span class="p">,</span><span class="n">n</span><span class="p">);</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">ss</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> 
        <span class="p">(</span><span class="n">x</span><span class="o">+=</span><span class="n">m</span><span class="p">)</span><span class="o">%=</span><span class="n">n</span><span class="p">;</span>
    <span class="n">printf</span><span class="p">(</span><span class="s">&quot;%d&quot;</span><span class="p">,</span><span class="n">x</span><span class="p">);</span>
    <span class="k">return</span> <span class="mi">0</span> <span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>题面</p>
<p><img src="https://s1.ax1x.com/2017/10/26/UJD0g.png" alt="">
<img src="https://s1.ax1x.com/2017/10/26/UJr7Q.png" alt=""></p>
<p>概括一下题面:求逆序对.</p>
<p>蒟蒻考试爆0,硬是没想到要求逆序对.<del>问了一下省队爷,省队爷说这不是显然的么...</del></p>
<p>两列火柴之间的距离与高度差的平方有关,交换是的距离变小,次数要%99999997(1e9-3),要求交换相邻的火柴.</p>
<p>高度</p>
<p>$$2^{31}-1$$</p>
<p>考试的时候以为是dp,<del>然后觉得稳了,放心的开始码</del>GG.</p>
<p>实际上确实是裸的求逆序对,首先要知道,交换第一列还是交换第二列性质是一样的.</p>
<p>对于一组数据</p>
<p>第一列 a b</p>
<p>第二列 c d</p>
<p>a &gt; b , c &gt; d</p>
<p>我们是否需要交换a,b?</p>
<p>当
ac+bd&gt;ad+bc
时.就说明需要交换</p>
<blockquote><p>证明:
c&gt;d a&gt;b</p>
<p>c-d&gt;0</p>
<p>a(c-d)&gt;b(c-d)</p>
<p>ac-ad&gt;bc-bd</p>
<p>ac+bd&gt;bc+ad</p>
</blockquote>
<p>得证ac+bd&gt;bc+ad,所以需要交换</p>
<p>以上就是说一个逆序对要交换一次,那么只用求出有多少个逆序对就可以知道最少要交换多少次了</p>
<p>所以.</p>
<p>裸的逆序对</p>
<div class="highlight"><pre><span></span><span class="cp">#include</span><span class="cpf">&lt;cstdio&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;algorithm&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cstring&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cmath&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;iostream&gt;</span><span class="cp"></span>
<span class="k">const</span> <span class="kt">int</span> <span class="n">lxn</span><span class="o">=</span><span class="mi">99999997</span><span class="p">;</span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="k">template</span><span class="o">&lt;</span><span class="k">class</span> <span class="nc">T</span><span class="o">&gt;</span><span class="kt">void</span> <span class="n">read</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">){</span>
    <span class="n">x</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">int</span> <span class="n">f</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">char</span> <span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;</span><span class="sc">&#39;0&#39;</span><span class="o">||</span><span class="n">ch</span><span class="o">&gt;</span><span class="sc">&#39;9&#39;</span><span class="p">)</span><span class="n">f</span><span class="o">|=</span><span class="p">(</span><span class="n">ch</span><span class="o">==</span><span class="sc">&#39;-&#39;</span><span class="p">),</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;=</span><span class="sc">&#39;9&#39;</span><span class="o">&amp;&amp;</span><span class="n">ch</span><span class="o">&gt;=</span><span class="sc">&#39;0&#39;</span><span class="p">)</span><span class="n">x</span><span class="o">=</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">3</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">ch</span><span class="o">^</span><span class="mi">48</span><span class="p">),</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();</span>
    <span class="n">x</span><span class="o">=</span><span class="n">f</span><span class="o">?-</span><span class="nl">x</span><span class="p">:</span><span class="n">x</span><span class="p">;</span>
    <span class="k">return</span><span class="p">;</span>
<span class="p">}</span>

<span class="k">struct</span> <span class="n">node</span><span class="p">{</span>
    <span class="kt">int</span> <span class="n">pos</span><span class="p">,</span><span class="n">val</span><span class="p">;</span>
<span class="p">}</span><span class="n">a</span><span class="p">[</span><span class="mi">100010</span><span class="p">],</span><span class="n">b</span><span class="p">[</span><span class="mi">100010</span><span class="p">];</span>

<span class="kt">int</span> <span class="n">n</span><span class="p">,</span><span class="n">m</span><span class="p">,</span><span class="n">tree</span><span class="p">[</span><span class="mi">100010</span><span class="p">],</span><span class="n">rk</span><span class="p">[</span><span class="mi">100010</span><span class="p">];</span>

<span class="kt">bool</span> <span class="nf">cmp</span><span class="p">(</span><span class="n">node</span> <span class="n">a</span><span class="p">,</span><span class="n">node</span> <span class="n">b</span><span class="p">){</span><span class="k">return</span> <span class="n">a</span><span class="p">.</span><span class="n">val</span><span class="o">&gt;</span><span class="n">b</span><span class="p">.</span><span class="n">val</span><span class="p">;}</span>

<span class="kt">int</span> <span class="nf">lb</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">){</span><span class="k">return</span> <span class="n">x</span><span class="o">&amp;</span><span class="p">(</span><span class="o">-</span><span class="n">x</span><span class="p">);}</span>

<span class="kt">int</span> <span class="nf">sum</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">){</span><span class="kt">int</span> <span class="n">ans</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="k">for</span><span class="p">(;</span><span class="n">x</span><span class="p">;</span><span class="n">x</span><span class="o">-=</span><span class="n">lb</span><span class="p">(</span><span class="n">x</span><span class="p">))</span><span class="n">ans</span><span class="o">+=</span><span class="n">tree</span><span class="p">[</span><span class="n">x</span><span class="p">];</span><span class="k">return</span> <span class="n">ans</span><span class="p">;}</span>

<span class="kt">void</span> <span class="nf">pus</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">){</span><span class="k">for</span><span class="p">(;</span><span class="n">x</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">x</span><span class="o">+=</span><span class="n">lb</span><span class="p">(</span><span class="n">x</span><span class="p">))</span><span class="n">tree</span><span class="p">[</span><span class="n">x</span><span class="p">]</span><span class="o">++</span><span class="p">;}</span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span>
<span class="p">{</span>
    <span class="n">freopen</span><span class="p">(</span><span class="s">&quot;match.in&quot;</span><span class="p">,</span><span class="s">&quot;r&quot;</span><span class="p">,</span><span class="n">stdin</span><span class="p">);</span>
    <span class="n">freopen</span><span class="p">(</span><span class="s">&quot;match.out&quot;</span><span class="p">,</span><span class="s">&quot;w&quot;</span><span class="p">,</span><span class="n">stdout</span><span class="p">);</span>
    <span class="kt">int</span> <span class="n">ans</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
    <span class="n">read</span><span class="p">(</span><span class="n">n</span><span class="p">);</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">read</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">val</span><span class="p">),</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">pos</span><span class="o">=</span><span class="n">i</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">read</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">val</span><span class="p">),</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">pos</span><span class="o">=</span><span class="n">i</span><span class="p">;</span>
    <span class="n">sort</span><span class="p">(</span><span class="n">a</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="n">a</span><span class="o">+</span><span class="mi">1</span><span class="o">+</span><span class="n">n</span><span class="p">,</span><span class="n">cmp</span><span class="p">);</span>
    <span class="n">sort</span><span class="p">(</span><span class="n">b</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="n">b</span><span class="o">+</span><span class="mi">1</span><span class="o">+</span><span class="n">n</span><span class="p">,</span><span class="n">cmp</span><span class="p">);</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">rk</span><span class="p">[</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">pos</span><span class="p">]</span><span class="o">=</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">pos</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
        <span class="n">ans</span><span class="o">=</span><span class="p">(</span><span class="n">ans</span><span class="o">+</span><span class="p">(</span><span class="n">sum</span><span class="p">(</span><span class="n">n</span><span class="p">)</span><span class="o">-</span><span class="n">sum</span><span class="p">(</span><span class="n">rk</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">)))</span><span class="o">%</span><span class="n">lxn</span><span class="p">;</span>
        <span class="n">pus</span><span class="p">(</span><span class="n">rk</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span>
    <span class="p">}</span>
    <span class="n">printf</span><span class="p">(</span><span class="s">&quot;%d</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="n">ans</span><span class="p">);</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> 
<span class="p">}</span>
</pre></div>
<p>树状数组求逆序对美滋滋</p>
<p>题面</p>
<p><img src="https://s1.ax1x.com/2017/10/26/UYAjf.png" alt=""></p>
<p><del>前面在默写Dinic板子,一看到这道题,鸡冻啊,那这样是不是要q遍Dinic,那不是就30分GG么,这年头Noip2013年的题,Dinic只能拿30分了么.</del></p>
<p>所以头不行</p>
<p>q次询问两个点之间的最大链的最小值.</p>
<p>那么既然是最大链,一定在最大生成树,-1就是两者不在一个集合.所以一个变形Kruskal求一下最大生成树,然后建树跑边就行.</p>
<p>只用寻找给定两个点中最大链的最小值就是道路的最大载重喽.</p>
<p>所以似乎有三种方法可以A</p>
<p>1、爆搜(显然这个是过不了的)</p>
<p>$$O(xuanxue)$$</p>
<p>2、暴力树上增</p>
<p>$$O(N)$$</p>
<p>3、LCA</p>
<p>$$O(Log_2N)$$</p>
<p>4、树链剖分</p>
<p>$$O(Log_2N)$$</p>
<div class="highlight"><pre><span></span><span class="cp">#include</span><span class="cpf">&lt;cstdio&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cstring&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cmath&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;iostream&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;algorithm&gt;</span><span class="cp"></span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="k">template</span><span class="o">&lt;</span><span class="k">class</span> <span class="nc">T</span><span class="o">&gt;</span><span class="kt">void</span> <span class="n">read</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">){</span>
    <span class="n">x</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">int</span> <span class="n">f</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">char</span> <span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;</span><span class="sc">&#39;0&#39;</span><span class="o">||</span><span class="n">ch</span><span class="o">&gt;</span><span class="sc">&#39;9&#39;</span><span class="p">){</span><span class="n">f</span><span class="o">|=</span><span class="p">(</span><span class="n">ch</span><span class="o">==</span><span class="sc">&#39;-&#39;</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;=</span><span class="sc">&#39;9&#39;</span><span class="o">&amp;&amp;</span><span class="n">ch</span><span class="o">&gt;=</span><span class="sc">&#39;0&#39;</span><span class="p">){</span><span class="n">x</span><span class="o">=</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">3</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">ch</span><span class="o">^</span><span class="mi">48</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="n">x</span><span class="o">=</span><span class="n">f</span><span class="o">?-</span><span class="nl">x</span><span class="p">:</span><span class="n">x</span><span class="p">;</span>
    <span class="k">return</span> <span class="p">;</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="n">n</span><span class="p">,</span><span class="n">m</span><span class="p">,</span><span class="n">fx</span><span class="p">[</span><span class="mi">100010</span><span class="p">],</span><span class="n">f</span><span class="p">[</span><span class="mi">30</span><span class="p">][</span><span class="mi">50010</span><span class="p">],</span><span class="n">head</span><span class="p">[</span><span class="mi">50010</span><span class="p">],</span><span class="n">ecnt</span><span class="p">,</span><span class="n">deep</span><span class="p">[</span><span class="mi">10010</span><span class="p">],</span><span class="n">sum</span><span class="p">[</span><span class="mi">22</span><span class="p">][</span><span class="mi">10001</span><span class="p">];</span>

<span class="k">struct</span> <span class="n">node</span><span class="p">{</span>
    <span class="kt">int</span> <span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">,</span><span class="n">w</span><span class="p">;</span>
<span class="p">}</span><span class="n">ss</span><span class="p">[</span><span class="mi">100010</span><span class="p">];</span>

<span class="k">struct</span> <span class="n">edge</span><span class="p">{</span>
    <span class="kt">int</span> <span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">,</span><span class="n">w</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">next</span><span class="p">;</span>
<span class="p">}</span><span class="n">E</span><span class="p">[</span><span class="mi">100010</span><span class="p">];</span>

<span class="kt">void</span> <span class="nf">addedge</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span><span class="kt">int</span> <span class="n">w</span><span class="p">){</span>
    <span class="n">E</span><span class="p">[</span><span class="o">++</span><span class="n">ecnt</span><span class="p">].</span><span class="n">u</span><span class="o">=</span><span class="n">u</span><span class="p">;</span>
    <span class="n">E</span><span class="p">[</span><span class="n">ecnt</span><span class="p">].</span><span class="n">v</span><span class="o">=</span><span class="n">v</span><span class="p">;</span>
    <span class="n">E</span><span class="p">[</span><span class="n">ecnt</span><span class="p">].</span><span class="n">w</span><span class="o">=</span><span class="n">w</span><span class="p">;</span>
    <span class="n">E</span><span class="p">[</span><span class="n">ecnt</span><span class="p">].</span><span class="n">next</span><span class="o">=</span><span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">];</span>
    <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">]</span><span class="o">=</span><span class="n">ecnt</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="nf">fid</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">){</span><span class="k">return</span> <span class="n">fx</span><span class="p">[</span><span class="n">x</span><span class="p">]</span><span class="o">==</span><span class="n">x</span><span class="o">?</span><span class="nl">x</span><span class="p">:</span><span class="n">fx</span><span class="p">[</span><span class="n">x</span><span class="p">]</span><span class="o">=</span><span class="n">fid</span><span class="p">(</span><span class="n">fx</span><span class="p">[</span><span class="n">x</span><span class="p">]);}</span>

<span class="kt">bool</span> <span class="nf">cmp</span><span class="p">(</span><span class="n">node</span> <span class="n">a</span><span class="p">,</span><span class="n">node</span> <span class="n">b</span><span class="p">){</span><span class="k">return</span> <span class="n">a</span><span class="p">.</span><span class="n">w</span><span class="o">&gt;</span><span class="n">b</span><span class="p">.</span><span class="n">w</span><span class="p">;}</span>

<span class="kt">void</span> <span class="nf">Kruskal</span><span class="p">()</span>
<span class="p">{</span>
    <span class="n">sort</span><span class="p">(</span><span class="n">ss</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="n">ss</span><span class="o">+</span><span class="mi">1</span><span class="o">+</span><span class="n">m</span><span class="p">,</span><span class="n">cmp</span><span class="p">);</span>
    <span class="kt">int</span> <span class="n">cnt</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
        <span class="kt">int</span> <span class="n">dx</span><span class="o">=</span><span class="n">fid</span><span class="p">(</span><span class="n">ss</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">u</span><span class="p">);</span><span class="kt">int</span> <span class="n">dy</span><span class="o">=</span><span class="n">fid</span><span class="p">(</span><span class="n">ss</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">v</span><span class="p">);</span>
        <span class="k">if</span><span class="p">(</span><span class="n">dx</span><span class="o">!=</span><span class="n">dy</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">fx</span><span class="p">[</span><span class="n">dx</span><span class="p">]</span><span class="o">=</span><span class="n">dy</span><span class="p">;</span><span class="n">cnt</span><span class="o">++</span><span class="p">;</span>
            <span class="n">addedge</span><span class="p">(</span><span class="n">ss</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">u</span><span class="p">,</span><span class="n">ss</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">v</span><span class="p">,</span><span class="n">ss</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">w</span><span class="p">);</span>
            <span class="n">addedge</span><span class="p">(</span><span class="n">ss</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">v</span><span class="p">,</span><span class="n">ss</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">u</span><span class="p">,</span><span class="n">ss</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">w</span><span class="p">);</span>
        <span class="p">}</span>
        <span class="k">if</span><span class="p">(</span><span class="n">cnt</span><span class="o">==</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="k">break</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="p">;</span>   
<span class="p">}</span>

<span class="kt">void</span> <span class="nf">dfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span><span class="kt">int</span> <span class="n">fx</span><span class="p">){</span>
    <span class="n">f</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="n">x</span><span class="p">]</span><span class="o">=</span><span class="n">fx</span><span class="p">;</span>
    <span class="n">deep</span><span class="p">[</span><span class="n">x</span><span class="p">]</span><span class="o">=</span><span class="n">deep</span><span class="p">[</span><span class="n">fx</span><span class="p">]</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">head</span><span class="p">[</span><span class="n">x</span><span class="p">];</span><span class="n">i</span><span class="p">;</span><span class="n">i</span><span class="o">=</span><span class="n">E</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">next</span><span class="p">){</span>
        <span class="kt">int</span> <span class="n">v</span><span class="o">=</span><span class="n">E</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">v</span><span class="p">;</span>
        <span class="k">if</span><span class="p">(</span><span class="n">v</span><span class="o">==</span><span class="n">fx</span><span class="p">)</span> <span class="k">continue</span><span class="p">;</span>
        <span class="n">sum</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="n">v</span><span class="p">]</span><span class="o">=</span><span class="n">E</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">w</span><span class="p">;</span>
        <span class="n">dfs</span><span class="p">(</span><span class="n">v</span><span class="p">,</span><span class="n">x</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="p">;</span>
<span class="p">}</span>

<span class="kt">void</span> <span class="nf">init</span><span class="p">()</span>
<span class="p">{</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
        <span class="k">if</span><span class="p">(</span><span class="n">fid</span><span class="p">(</span><span class="n">i</span><span class="p">)</span><span class="o">==</span><span class="n">i</span><span class="p">)</span>
            <span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="n">i</span><span class="p">);</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="mi">20</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">j</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">){</span>
            <span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span><span class="o">=</span><span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">]];</span>
            <span class="n">sum</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span><span class="o">=</span><span class="n">min</span><span class="p">(</span><span class="n">sum</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">],</span><span class="n">sum</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">]]);</span>
        <span class="p">}</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="nf">lca</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span><span class="kt">int</span> <span class="n">y</span><span class="p">){</span>
    <span class="kt">int</span> <span class="n">ans</span><span class="o">=</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">30</span><span class="p">;</span>
    <span class="k">if</span><span class="p">(</span><span class="n">deep</span><span class="p">[</span><span class="n">x</span><span class="p">]</span><span class="o">&gt;</span><span class="n">deep</span><span class="p">[</span><span class="n">y</span><span class="p">])</span> <span class="n">swap</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="n">y</span><span class="p">);</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">20</span><span class="p">;</span><span class="o">~</span><span class="n">i</span><span class="p">;</span><span class="n">i</span><span class="o">--</span><span class="p">)</span>
        <span class="k">if</span><span class="p">(</span><span class="n">deep</span><span class="p">[</span><span class="n">x</span><span class="p">]</span><span class="o">&lt;=</span><span class="n">deep</span><span class="p">[</span><span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">y</span><span class="p">]]){</span>
            <span class="n">ans</span><span class="o">=</span><span class="n">min</span><span class="p">(</span><span class="n">ans</span><span class="p">,</span><span class="n">sum</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">y</span><span class="p">]);</span>
            <span class="n">y</span><span class="o">=</span><span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">y</span><span class="p">];</span>
        <span class="p">}</span>
    <span class="k">if</span><span class="p">(</span><span class="n">x</span><span class="o">==</span><span class="n">y</span><span class="p">)</span> <span class="k">return</span> <span class="n">ans</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">20</span><span class="p">;</span><span class="o">~</span><span class="n">i</span><span class="p">;</span><span class="n">i</span><span class="o">--</span><span class="p">)</span>
        <span class="k">if</span><span class="p">(</span><span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">x</span><span class="p">]</span><span class="o">!=</span><span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">y</span><span class="p">]){</span>
            <span class="n">ans</span><span class="o">=</span><span class="n">min</span><span class="p">(</span><span class="n">sum</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">x</span><span class="p">],</span><span class="n">min</span><span class="p">(</span><span class="n">ans</span><span class="p">,</span><span class="n">sum</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">y</span><span class="p">]));</span>
            <span class="n">x</span><span class="o">=</span><span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">x</span><span class="p">];</span>
            <span class="n">y</span><span class="o">=</span><span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">y</span><span class="p">];</span>
        <span class="p">}</span>
    <span class="n">ans</span><span class="o">=</span><span class="n">min</span><span class="p">(</span><span class="n">ans</span><span class="p">,</span><span class="n">min</span><span class="p">(</span><span class="n">sum</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="n">x</span><span class="p">],</span><span class="n">sum</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="n">y</span><span class="p">]));</span>
    <span class="k">return</span> <span class="n">ans</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span>
<span class="p">{</span>
    <span class="n">freopen</span><span class="p">(</span><span class="s">&quot;truck.in&quot;</span><span class="p">,</span><span class="s">&quot;r&quot;</span><span class="p">,</span><span class="n">stdin</span><span class="p">);</span>
    <span class="n">freopen</span><span class="p">(</span><span class="s">&quot;truck.out&quot;</span><span class="p">,</span><span class="s">&quot;w&quot;</span><span class="p">,</span><span class="n">stdout</span><span class="p">);</span>
    <span class="n">memset</span><span class="p">(</span><span class="n">sum</span><span class="p">,</span><span class="mh">0x3f3f3f3f</span><span class="p">,</span><span class="k">sizeof</span><span class="p">(</span><span class="n">sum</span><span class="p">));</span>
    <span class="n">read</span><span class="p">(</span><span class="n">n</span><span class="p">),</span><span class="n">read</span><span class="p">(</span><span class="n">m</span><span class="p">);</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">fx</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">=</span><span class="n">i</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
        <span class="kt">int</span> <span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">,</span><span class="n">w</span><span class="p">;</span>
        <span class="n">read</span><span class="p">(</span><span class="n">ss</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">u</span><span class="p">),</span><span class="n">read</span><span class="p">(</span><span class="n">ss</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">v</span><span class="p">),</span><span class="n">read</span><span class="p">(</span><span class="n">ss</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">w</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="n">Kruskal</span><span class="p">();</span>
    <span class="n">init</span><span class="p">();</span>
    <span class="kt">int</span> <span class="n">q</span><span class="p">;</span><span class="n">read</span><span class="p">(</span><span class="n">q</span><span class="p">);</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">q</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
        <span class="kt">int</span> <span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">;</span>
        <span class="n">read</span><span class="p">(</span><span class="n">u</span><span class="p">),</span><span class="n">read</span><span class="p">(</span><span class="n">v</span><span class="p">);</span>
        <span class="k">if</span><span class="p">(</span><span class="n">fid</span><span class="p">(</span><span class="n">u</span><span class="p">)</span><span class="o">!=</span><span class="n">fid</span><span class="p">(</span><span class="n">v</span><span class="p">))</span> <span class="n">printf</span><span class="p">(</span><span class="s">&quot;-1</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">);</span>
        <span class="k">else</span> <span class="n">printf</span><span class="p">(</span><span class="s">&quot;%d</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="n">lca</span><span class="p">(</span><span class="n">u</span><span class="p">,</span><span class="n">v</span><span class="p">));</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="mi">0</span> <span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>By:Wahacer</p>
<p>2017.10.26</p>
<p>15:30</p>
<p>"一腔热血.满腹情怀.一无所成."</p>


        </div>
  </div>
</div>
<!-- Footer
    ================================================== -->
<footer class="footer">
  <div class="container">
         Copyright (c) 2017 Powered By <a href="https://gitee.com/uncle-lu/oub">OUB</a>
         <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/"><img alt="知识共享许可协议" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/3.0/cn/88x31.png" /></a><br />本作品采用<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/">知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议</a>进行许可。
  </div>
</footer>
<script>
    $('h1').each(function() {
        $(this).wrap('<section id="' + this.id + '"/>');
    });

    $('h1').wrap('<div class="page-header" />');
    $('h1').wrap('<div class="well well-small" />');

    $(document).ready(function() {
        var items = [];
        $('h1').each(function() {
            items.push('<li><a href="#' + this.id + '"><i class="fa fa-chevron-right pull-right"></i> ' + $(this).text() + '</a></li>');
        });  // close each()

    $('#sidebar_list').append( items.join('') );

    $('table').each(function() {
        $(this).addClass('table table-striped table-condensed table-hover');
    });

    $('.done0').each(function() {
        $(this).html('<div class="alert alert-info"><i class="fa fa-check-square-o"></i>'+$(this).html()+'</div></li>');
    });

    $('.done4').each(function() {
        $(this).html('<div class="alert alert-success"><i class="fa fa-square-o"></i>'+$(this).html()+'</div></li>');
    });
   
    $('pre').each(function() {
        $(this).html('<code>'+$(this).html()+'</code>');
    });
    hljs.initHighlightingOnLoad();
});
</script>
</body>
</html>